package com.lz.learning;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 前缀和技巧
 * <p>
 * 数组[1,1,1] 求连续和 2
 * 输出 2
 */
public class PrefixSum {

    public static void main(String[] args) {

        PrefixSum prefixSum = new PrefixSum();
        prefixSum.PrefixSum02(new int[]{1, 1, 1}, 2);

        prefixSum.statisticsScore(new int[]{15,101,109,110,113});
    }

    /**
     * fail
     *
     * @param array
     * @param target
     * @return
     */
    int Sum(int[] array, int target) {

        for (int i = 0; i < array.length; i++) {

        }
        return 0;
    }

    int PrefixSum(int[] array, int target) {
        int[] preSum = new int[array.length + 1];

        for (int i = 0; i < array.length; i++) {
            preSum[i + 1] = preSum[i] + array[i];
        }
        int res = 0;
        for (int i = 0; i < preSum.length; i++) {
            for (int j = 0; j < j; j++) {
                if (preSum[i] - preSum[j] == target) {
                    res++;
                }
            }
        }
        System.out.println(res);
        return res;
    }

    /**
     * hash表做优化
     *
     * @param array
     * @param target
     * @return
     */
    int PrefixSum02(int[] array, int target) {
        int[] preSum = new int[array.length + 1];

        for (int i = 0; i < array.length; i++) {
            preSum[i + 1] = preSum[i] + array[i];
        }
        int res = 0;
        // 优化
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < preSum.length; i++) {
//            for (int j = 0; j < j; j++) {
//                if (preSum[i] - preSum[j] == target) {
//                    res++;
//                }
//            }
            /**
             *  等同于无序数组两数相加
             */
            int i1 = preSum[i];
            int i2 = i1 - target;
            if (map.containsKey(i2)) {
                Integer integer = map.get(i2);
                res += integer;
            }
            map.put(i1, map.getOrDefault(i1, 0) + 1);


        }
        System.out.println(res);
        return res;
    }

    /**
     * scores[15,101,109,110,113]
     *
     * @param scores
     */
    void statisticsScore(int[] scores) {
// 试卷满分 150 分
        int[] count = new int[150 + 1];
// 记录每个分数有几个同学
        for (int score : scores)
            count[score]++;
// 构造前缀和
        for (int i = 1; i < count.length; i++)
            count[i] = count[i] + count[i - 1];
        System.out.println(Arrays.toString(count));
       // [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
        // 用后一个区间 - 前一个区间

    }
}
